package Solutions

func bstToGst(root *TreeNode) *TreeNode {
	var p int
	return bstToGst_(root, &p)
}

func bstToGst_(root *TreeNode, RightSum *int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Right != nil {
		bstToGst_(root.Right, RightSum)
	}
	root.Val += *RightSum
	*RightSum = root.Val
	if root.Left != nil {
		bstToGst_(root.Left, RightSum)
	}
	return root
}